package com.laotang.第_1_章_数组和字符串.力扣_151_反转字符串里的单词;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class _151_reverse_words_in_a_string {
    // 使用内置 API
    // 时间复杂度：O(n)
    // 空间复杂度：O(n)
    public String reverseWords1(String s) {
        /*
        输入：s = "  Bob    Loves  Alice   "
        1. "Bob    Loves  Alice"
        2. ["Bob", "Loves", "Alice"]
        3. ["Alice", "Loves", "Bob"]
        4. "Alice Loves Bob"
        输出："Alice Loves Bob"
         */
        s = s.trim();
        List<String> list = Arrays.asList(s.split("\\s+"));
        Collections.reverse(list);
        return String.join(" ", list);
    }

    // 不使用内置 API
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)
    public String reverseWords(String s) {
        /*
        输入：s = "  Bob    Loves  Alice   "
        1. "Bob Loves Alice"
        2. "ecilA sevoL boB"
        3. "Alice Loves Bob"
        输出："Alice Loves Bob"
         */
        s = trim(s);

        char[] chars = s.toCharArray();
        reverse(chars, 0, chars.length - 1);

        return reverseEachWord(chars);
    }

    private String reverseEachWord(char[] chars) {
        int n = chars.length;
        int slow = 0, fast = 0;

        while (fast < n) {
            while (fast < n && chars[fast] != ' ') fast++;
            reverse(chars, slow, fast - 1);
            fast++;
            slow = fast;
        }

        return new String(chars);
    }

    private void reverse(char[] chars, int left, int right) {
        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }

    // 删除字符串中所有的空字符，但是单词之间需要一个空字符隔开
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)，原地删除空字符
    public String trim(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int slow = 0, fast = 0;

        while (fast < n) {
            if (chars[fast] != ' ' || (fast >= 1 && chars[fast - 1] != ' ')) {
                chars[slow] = chars[fast];
                slow++;
            }
            fast++;
        }

        if (slow >= 1 && chars[slow - 1] == ' ') slow--;

        return new String(chars, 0, slow);
    }
}
